#include <string>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <time.h>
#include "Permutation.h"
#include "Permutations.h"

#pragma warning (disable: 4996) //function or variable may be unsafe


using std::string;
using std::iostream;
using std::stringstream;
using std::endl;


Permutations::Permutations(VERTEX_SIZE *originalPermutation, int wordLen = 1, int wordWeight = 0, 
						   int groupSize = 1, int maxIntersectionForSave = 1, 
						   int minChainLengthForSave = 1, int maxChains=1,
						   double permutationPercent = 1.0)
: 
m_WordLen(wordLen), m_WordWeight(wordWeight),
m_OriginalGroupSize(groupSize), m_MaxIntersectionForSave(maxIntersectionForSave), 
m_MinChainLengthForSave(minChainLengthForSave), m_MaxChains(maxChains), m_PermutationPercent(permutationPercent)
{
	Permutation *perm;
	try
	{
		perm = new Permutation(originalPermutation,wordLen,groupSize,1);
	}
	catch(std::bad_alloc *e)
	{
		e = NULL; //to avoid compiler warning
		Debug::PrintDebugMsg("memory allocation failed  while creating permutations object - while saving original permutation");
		throw(new GraphColoringException("memory allocation failed!"));
	}
	m_Permutations.insert(m_Permutations.begin(),*perm);
}

//Permutations::~Permutations(void)
//{ }

int Permutations::GetGroupSize() const
{
	return m_OriginalGroupSize;
}
void Permutations::InsertPerm(const Permutation &perm)
{
	m_Permutations.push_back(perm);
}

Permutation *Permutations::GetOriginalPermutation()
{
	if (m_Permutations.empty())
	{
		return NULL;
	}
	else 
	{	
		return &(m_Permutations[0]);
	}
}

// This functions creates all the permutations and links between them
// The algorithm links a permutation to all permutations created before it with small intersections
// To go over all permutations and find chains we have to start from the 1st one and go over the list
void Permutations::Fill()
{
	if (m_Permutations.empty())
	{	
		return;
	}

	Permutation *original = GetOriginalPermutation();
	if (original == NULL)
	{
		Debug::PrintDebugMsg("Could not get original permutation to start filling, returning");
		return;
	}

	Permutation *nextPerm = original->NextPermutation();
	if(nextPerm == NULL)
	{
		Debug::PrintDebugMsg("Could not get the next permutation to start filling, returning");
		return;
	}

	int currentPermName = 2; // 1st perm is 1
	
	unsigned long long  factorial = CalcFactorial(m_WordLen);
	if(factorial == 0)
	{
		Logger::LogMessage("binary word is too long for application. factorial calculation is too big.");
		return;
	}

	double percent = m_PermutationPercent / 100;
	unsigned long long numberOfPermutaionsToCreate = (unsigned long long)(percent * factorial);
	
	std::stringstream stream;
	
	stream<<"Creating "<<m_PermutationPercent<<"% of permutations, total "<<numberOfPermutaionsToCreate;
	Logger::LogMessage(stream.str());
	stream.str("");

	for(int i=0; i < numberOfPermutaionsToCreate; i++)
	{	
		// Check if we want to save this permutation
		original = GetOriginalPermutation();
		if (original == NULL)
		{
			// Something is wrong with the permutation calc, maybe memory issue. we can not keep trying.
			Debug::PrintDebugMsg("Could not get next permutation while filling permutations, breaking");
			break;
		}

		int intersectionWithOriginal = nextPerm->CountIntersection(original->GetMatrixRows(),m_OriginalGroupSize);
		if (intersectionWithOriginal <= m_MaxIntersectionForSave)
		{
			AddPermutationToList(nextPerm,intersectionWithOriginal);
		}
		
		Permutation *tmp = nextPerm->NextPermutation();
		delete nextPerm;
		nextPerm = tmp;
		if(nextPerm == NULL)
		{
			Debug::PrintDebugMsg("Could not get the next permutation. returning");
			return;
		}

		if ( (i+1) % 100 == 0)
		{
			stream<<"Created "<<i+1<<" permutations";
			Logger::LogMessage(stream.str());
			stream.str("");
		}
	}
}

//--------------------------------------------------------------------------
// CreateAllChains - creates all chains
// for each chain creats output file with it's results.
//--------------------------------------------------------------------------
void Permutations::CreateAllChains(string chainFileNamePrefix)
{
	m_ChainFileNamePrefix = chainFileNamePrefix;
	Chain tempChain(m_MaxIntersectionForSave);
	Permutation* perm = GetOriginalPermutation(); 
	if (perm == NULL)
	{
		Debug::PrintDebugMsg("Could not get original permutation while starting to create chains, returning");
		return;
	}
	tempChain.PushPermutation(perm);

	if(!m_Chains.empty())
		m_Chains.clear();
	
	CreateChains(perm,tempChain,0);

	if(!m_Chains.empty())
		m_Chains.clear();
}

//--------------------------------------------------------------------------
// CreateChains: recursive function for creating chains
// Parameters: 
// perm - current permutation to work with
// chain - current chain
// chaincount - chain index for chain name (how many chains were saved)
// returns: updated chain count
//--------------------------------------------------------------------------
int Permutations::CreateChains(Permutation *perm, Chain chain, int chainCount)
{
	vector<RelatedPermutation>::iterator it = perm->GetRelatedPermsBegin();
	stringstream chainName;
	// Try to add all related perms
	for (; it< perm->GetRelatedPermsEnd(); it++)
	{
		// Group index is 1 based, vector is 0 based
		Permutation *newPerm = &m_Permutations[it->GetIndex()-1];
		if (chain.IsLegalToAdd(newPerm))
		{
			// Add new matrix to chain
			chain.PushPermutation(newPerm);
			chainCount = CreateChains(newPerm,chain,chainCount);
			// Remove new matrix from chain - all options with it were checked recursively
			chain.PopPermutation();
		}
		// Stop trying if we have enough chains
		if (chainCount >= m_MaxChains)
		{
			return chainCount;
		}
	}
	// Only save if this chain is long enough
	if (chain.GetLength() >= m_MinChainLengthForSave)
	{
		Chain *copyForSave = chain.Clone();
		if (copyForSave == NULL)
		{
			Debug::PrintDebugMsg("Could not clone matrix copy for save, not saving");
			return chainCount;
		}

		copyForSave->RemoveIntersections();

		// Recheck that chain is long enough
		if (copyForSave->GetLength() >= m_MinChainLengthForSave)
		{
			// Check if chain already exists
			bool found = false;
			for (vector<Chain>::iterator it = m_Chains.begin(); it < m_Chains.end() && !found; it++)
			{
				if ((*it)==*copyForSave)
				{
					found = true;
				}
			}

			if (!found)
			{
				chainCount++;
				chainName.flush();
				chainName << "chain" << chainCount;
				copyForSave->SetName(chainName.str());
				// Save chain to chain file and chain list
				copyForSave->Save(m_WordLen, m_WordWeight, m_ChainFileNamePrefix);
				m_Chains.push_back(*copyForSave);
				Logger::LogMessage("Saved chain");
			}
		}		
	}
	return chainCount;
}

//--------------------------------------------------------------------------
/// AddPermutationTolist: Gets a permutation, checks if it is a new one 
//  if so, adds it to list
/// Assumes permutation is OK to add to original group, removes intersection with original group
//--------------------------------------------------------------------------
void Permutations::AddPermutationToList(Permutation *permToSave,int intersectionWithOriginal)
{
	Permutation *originalPerm  = GetOriginalPermutation(); // update pointers
	if (originalPerm == NULL)
	{
		Debug::PrintDebugMsg("Could not get original permutation when adding permuatation to list, not saving it");
		return;
	}
	int currentPermName = m_Permutations.size()+1; // Names are 1 based

	vector<int> permutationsToLinkTo;
	permutationsToLinkTo.push_back(1); // Add original group or this function wouldn't be called

	// Remove intersection with original from permutation
	VERTEX_SIZE *permWithoutIntersectionWithOriginal = Permutation::GetMatrixWithoutIntersection(permToSave->GetMatrixRows(), 
																permToSave->GetGroupSize(), originalPerm->GetMatrixRows(), 
																originalPerm->GetGroupSize(),
																intersectionWithOriginal);

	// If we got NULL, the whole group was removed, so it is useless
	if (NULL==permWithoutIntersectionWithOriginal)
	{
		return;
	}

	Permutation *copyPerm = new Permutation(permWithoutIntersectionWithOriginal, permToSave->GetWordLen(), permToSave->GetGroupSize()-intersectionWithOriginal, currentPermName);

	// Go over all permutations we already saved and list this one as related to them
	vector<Permutation>::iterator it = m_Permutations.begin();
	// 1st matrix is original one and we dealt with it
	it++;
	bool isDuplicatePermutation = false;
	while (it != m_Permutations.end() && !isDuplicatePermutation)
	{
		if (*copyPerm == *it)
		{
			isDuplicatePermutation = true;
		}

		int intersectionWithCurrentMatrix = copyPerm->CountIntersection(it->GetMatrixRows(),it->GetGroupSize());
		// Check if this is the same permutation - if their sizes match and the intersection is all the group
		// If one is bigger the chains they create will be different and we need both.
		if (copyPerm->GetGroupSize() == it->GetGroupSize() && intersectionWithCurrentMatrix == copyPerm->GetGroupSize()) 
		{
			isDuplicatePermutation = true;
		}

		if (!isDuplicatePermutation)
		{
			// If the intersection is small but this matrix is not contained in the other (or vice versa), link them
			if (intersectionWithCurrentMatrix <= m_MaxIntersectionForSave && intersectionWithCurrentMatrix != copyPerm->GetGroupSize() && intersectionWithCurrentMatrix != it->GetGroupSize())
			{
					permutationsToLinkTo.push_back(it->GetName());
			}
		}
		it++;
	}
	
	// If this isn't a duplicate permutation, go over the list and add it to each permutation there
	// Then add it to list
	if (!isDuplicatePermutation)
	{
		vector<int>::iterator it = permutationsToLinkTo.begin();
		for (; it!=permutationsToLinkTo.end(); it++)
		{
			int permToAddToIndex = *it-1;
			int intersectionWithCurrentMatrix = copyPerm->CountIntersection(m_Permutations[permToAddToIndex].GetMatrixRows(),m_Permutations[permToAddToIndex].GetGroupSize());

			// Add links to both permutations - this is important for recursive chain finding (the order of the chain matters)
			m_Permutations[permToAddToIndex].AddRelatedPerm(RelatedPermutation(copyPerm->GetName(),intersectionWithCurrentMatrix, copyPerm->GetGroupSize()));
			copyPerm->AddRelatedPerm(RelatedPermutation(*it,intersectionWithCurrentMatrix, m_Permutations[permToAddToIndex].GetGroupSize()));
		}

		//save
		m_Permutations.push_back(*copyPerm);
	}		
}

//--------------------------------------------------------------------------
// CreatePermutationsObject - creates a permutations object from given chain and parameters file 
//
// parameters : 
// chainFile - a file containing a chain inforamtion, that it's first chain is
//		the basic group from wiche we are stating the permutaions calculation
// inputFile - a file with general parameters for the permutaion calculation
//
// return - a Permutations object initilayezd acording to the given files content.
//--------------------------------------------------------------------------
Permutations *Permutations::CreatePermutationsObject(ChainParser& chainFile, InputParmetersParser& inputFile)
{
	try
	{
		// Find general parameters part and get word length
		int wordLen = chainFile.GetBinaryWordLength();
		int wordWeight = chainFile.GetBinaryWordWeight();

		vector<VERTEX_SIZE> initialPermVector;
		int groupSize = 0;
		
		if(chainFile.GetNumberOfGroups() > 0)
		{
			vector<bool> *nextVertex = chainFile.GetFirstVertex(1); //first group is the base group.
			while (nextVertex != NULL)
			{
					groupSize++;
					VERTEX_SIZE vertex = 0;
					for(int i=0; i < wordLen; i++)
					{
						int temp = ((*nextVertex)[i] == true) ? 1 : 0;
						vertex = vertex*2 + temp;
					}
					initialPermVector.push_back(vertex);						
					nextVertex = chainFile.GetNextVertex();
			}
			
			//check the group size
			int * groupSummary = chainFile.GetGroupSummary();
			if (groupSize != groupSummary[0])
			{
				Logger::LogMessage("chain Input file mismatch, group size doesn't match actual size for initial group");
				delete[] groupSummary;
				return 0;
			}
			delete[] groupSummary;
		}
		else
		{
			Logger::LogMessage("Initial group is empty ");
			return 0;
		}

		if (initialPermVector.size() == 0)
		{
			Logger::LogMessage("Initial group is empty ");
			return 0;
		}
		
		int minChainLenForSave	= inputFile.GetMinPermutationChainLength();
		int maxIntersectionSize = inputFile.GetIntersectionSize();
		int maxChains			= inputFile.GetChainNumber();
		double permutationPercent	= inputFile.GetPermutationPercent();

		if(permutationPercent > 100)
		{
			Logger::LogMessage("illegal input value for input variable: permutationPercent");
			return 0;
		}
		
		// copy to pointer
		VERTEX_SIZE *initialPerm;
		try
		{
			initialPerm	= new VERTEX_SIZE[groupSize];
		}
		catch(std::bad_alloc *e)
		{
			e = NULL; //to avoid compiler warning
			Debug::PrintDebugMsg("memory allocation failed  while loading initial permutation");
			throw(new GraphColoringException("memory allocation failed!"));
		}

		int i=0;
		for (vector<VERTEX_SIZE>::iterator it = initialPermVector.begin(); it < initialPermVector.end(); it++)
		{
			initialPerm[i] = (*it);
			i++;
		}
		Permutations *permutations;
		try
		{
			permutations = new Permutations(initialPerm,wordLen, wordWeight, 
											groupSize, maxIntersectionSize,
											minChainLenForSave, maxChains, permutationPercent);
		}
		catch(std::bad_alloc *e)
		{	
			e = NULL; //to avoid compiler warning
			Debug::PrintDebugMsg("memory allocation failed  while creating permutations objects");
			throw(new GraphColoringException("memory allocation failed!"));
		}
	
		return permutations;
	}
	catch(ChainParserExepetion &e) 
	{
		Logger::LogMessage(e.GetErrorDescription());
	}
	catch(InputParmetersParserExepetion &e) 
	{
		Logger::LogMessage(e.GetErrorDescription());
	}
	catch (GraphColoringException &e)
	{
		Logger::LogMessage(e.GetErrorDescription());
	}

	//if we are here, an error ocuerd
	return NULL;
}


//--------------------------------------------------------------------------
// Run - fills permutations object and creates all chains
// Parameters:
// outputFileName - file name for output
//--------------------------------------------------------------------------
void Permutations::Run()
{
	Fill();
	Logger::LogMessage("Done creating permutations, now searching for chains");
	CreateAllChains(GetCurrentTimeStamp()); // all outputs will be prefixed with the current date and time
	//SaveToFile(outputFileName);
}

//--------------------------------------------------------------------------
// GetCurrentTimeStamp
// Create filename from current timestamp
//-------------------------------------------------------------------------
string Permutations::GetCurrentTimeStamp()
{
	time_t rawtime;
	time(&rawtime);
    struct tm * timeinfo;
	timeinfo = localtime(&rawtime);
	char buffer[18];
	strftime (buffer,18,"%d-%m-%Y_%H-%M",timeinfo);
	string filename(buffer);

	return filename;
}

//--------------------------------------------------------------------------
// CalcFactorial
//-------------------------------------------------------------------------
unsigned long long Permutations::CalcFactorial(int base)
{
	if(base > 20)
		return 0;

	unsigned long long factorial = 1;
	for(int i=2; i <= base; i++ )
	{
		factorial *= i;
	}
	
	return factorial;
}